The invention relates to the field of Computer Aided Graphic Design (CAGD) applications, and more particularly, to deformable modeling of 2-manifold and non-manifold B-rep solid models within CAGD applications.
Deformable modeling of single surfaces in solid model CAGD applications is well known in the art. For example, George Celniker, xe2x80x9cShapeWright: Finite Element Based Free-Form Shape Designxe2x80x9d, M.I.T. Ph.D. Thesis, Department of Mechanical Engineering, September 1990 (xe2x80x9c[Celniker 90]xe2x80x9d) defines the basic notion of using a simulation-based approach that mimics a physical system to sculpt and design free-form surfaces. The work was limited to a particular surface type, the serendipity triangular surface, and to a limited set of constraints which included only those geometric properties which were explicitly described in the surface representation. These constraints included point constraints at the vertices of the triangular mesh for position, tangent and normal properties, as well as cubic curve constraints along the edges of the triangular mesh. The approach did not support trimmed curve constraints or a general approach to representing surfaces. George Celniker and Will Welch, xe2x80x9cLinear Constraints for Deformable B-Spline Surfacesxe2x80x9d, Proceedings of the 1992 Symposium on Interactive 3D Graphics, Cambridge Mass., Mar. 29,-Apr. 1, 1992 (xe2x80x9c[Celniker 92]xe2x80x9d) describes the extension of [Celniker 90] to B-Spline and NURB surfaces as well as trimmed curve constraints. These references do not describe methods for local or multiple-surface deformations.
Local deformation using hierarchical patches is also known in the art. Forsey, D. and Bartels, R. xe2x80x9cHierarchical B-Spline Refinementxe2x80x9d, Computer Graphics 22, 4, pages 205-212, August 1988 (xe2x80x9c[Forsey 88]xe2x80x9d) describes the notion of using hierarchical B-Spline and NURB surfaces to capture a local deformation capability. This work was limited to attaching child patches to a parent along the outer perimeter of the child patch. This limits this approach to supporting local deformations that occur within a rectangular region. W. Welch and A. Witkin, xe2x80x9cVariational Surface Modelingxe2x80x9d, Computer Graphics, 26(2): 157-166, 1992 (xe2x80x9c[Welch 92]xe2x80x9d) also demonstrates the use of deformable hierarchical patches but is similarly limited to rectangular patches along the outer perimeter of the child patch.
Neither [Forsey 88] nor [Welch 92] supports local deformations whose boundaries can be of any simple closed curve shape.
Simultaneous deformation of deformable multiple surfaces in a mesh of surfaces is also known in the art. [Welch 92] describes modeling in a B-rep solid modeling context with curve tracking that incorporates a multi-surface deformation. In [Welch 92], however, the surfaces being deformed do not load one another; instead, [Welch 92] requires that the curve constraint be shaped and then both surfaces deform to fit the curve. [Welch 92] is also restricted to curve constraints along an entire boundary of a surface.
In more recent developments, Hong Qin and Demetri Terzopolous, xe2x80x9cDynamic Manipulation of Triangular B-Splinesxe2x80x9d, Proceedings of the Third Symposium on Solid Modeling and Applications, Salt Lake City, Utah, May 17-191995 (xe2x80x9c[Qin 95]xe2x80x9d) shows an extension of the deformable modeling concepts to triangular B-spline surfaces and to the application of deformable modeling to solid model representations. This work also demonstrates the use of multi-surface deformations in and out of a solid modeling context. The deformable modeling multi-surface approach described in [Qin 95] uses a simple constraint mechanism to connect multiple patches into one large deformation network. This approach limits the nature of the meshes that can be deformed. Every edge within the mesh has to bound to one complete side of a triangular patch.
Neither [Welch 92] nor [Qin 95] supports a more general constraint mechanism used to connect the individual patches which would allow xe2x80x98Txe2x80x99 and xe2x80x98+xe2x80x99 style intersections within the mesh as well as supporting mesh edges which map to trimmed patch edges.
Because of the limitations of existing deformable modeling applications, there exists a continuing need to allow deformation in CAGD applications involving more flexible curve constraint mechanisms.
The present invention overcomes the limitations of the prior art by providing methods for deforming solid models in CAGD applications using a general curve constraint mechanism.
It is an object of this invention to allow local deformation within a surface by using hierarchical patches and a seam constraint to connect parent and child patches within a patch hierarchy. Deformable modeling is a global operation. Any change applied to the parameters of the problem will modify the shape of the entire curve or surface. In many design situations there is a need for a local operator. Consider the example of a car door design. Once a designer has created the shape of the door, the designer may want to add a small pocket to make room for a flush door handle. The end user will not want to modify the shape of the door while inserting this local feature shape. To support local deformations, we augment the deformable modeling algorithm with hierarchical curves and surfaces connected together with a set of curve constraints known as seam constraints.
A hierarchical curve or surface is a single shape that is represented by a set of hierarchically organized shapes. As an example, think of the front panel of a shirt that has a breast pocket. The outer shape of the shirt panel is made up in pieces. For the most part, the shape of the shirt comes from the shirt""s front panel. For a local region, the pocket shape defines the shape of the shirt. The pocket is connected to the panel across a seam. Along the seam, the shape of the panel and the shape of the pocket are the same. Away from the seam the shape of the panel and the shape of the pocket may vary.
A patch higher in the hierarchy, in this case the shirt front, is known as a parent patch. A patch directly below the parent patch in the hierarchy, in this case the shirt pocket, is known as a child patch. A seam constraint is used to ensure connectivity between a parent patch and a child patch during deformation. This seam constraint may be any simple closed loop curve in the domain space of both the parent and child patches.
It is a further object of this invention to allow multisurface deformation in a solid model by using a general curve constraint mechanism to link different surfaces. When working with B-rep solid models, end users will need to deform sets of faces simultaneously. We call this ability multisurface deformation. Multisurface deformation can make blends around sharp edges and corners and enable deforming a quilt of faces as if they were one single face.
The curve constraint mechanism is used to support multisurface deformations with the introduction of the idea of a link constraint. A link constraint is specified by two different curves that lie within the domain space of two different surfaces. The behavior of the constraint is to act like a zipper that connects the points along the length of the curves to one another, with various degrees of continuity. The curves represented by a link constraint can be any curves in the domain spaces of the surfaces to be deformed together, including trimmed curves, and partial edges of surfaces. This allows generalized meshes of surfaces to be deformed together, including surfaces meeting at xe2x80x9cTxe2x80x9dintersections and xe2x80x9c+xe2x80x9d intersections where the surfaces are not bounded, and also allows any number of surfaces to be linked together at a single vertex.